#include<iostream>
#include<algorithm>

#include "Graph.h"
#include "virtual_graph.h"

virtual_graph::~virtual_graph(){


};

void virtual_graph::SetupTopology(Graph *graph){
    graph_=graph;
    num_nodes_=graph->NodeSize();
    virtual_adjList=std::vector<std::vector<virtual_link *>>(num_nodes_+1);
};

void virtual_graph::makeVirtualGraph(){
    for(int i=1;i<=num_nodes_;i++){  //节点编号从1开始，储存位置也从1开始
        virtual_link *lk=new virtual_link(i,i);
        Dfs_virLink(i,lk);
        delete lk;
    }
    return;
}



void virtual_graph::Dfs_virLink(int i, virtual_link *lk){
    if(lk->cost>limit_cost){
        int type=graph_->GetNodeType(lk->ter_id);
        if(type==1){
            lk->cost +=100;
        }else if(type==2){
            lk->cost +=10;
        }else{
            return;
        }
        virtual_link *link=new virtual_link(lk);
        virtual_adjList[i].push_back(link);
        return;
    }

    for(Link *link:graph_->GetEgressLinks(lk->ter_id)){
        virtual_link *temp_lk=lk;
        int new_ter=link->ter_id;
        int new_cost=link->cost;
        int new_delay=link->delay;
        lk->cost += new_cost;
        lk->delay += new_delay;
        lk->nodes_passed.push_back(new_ter);
        lk->nodes_passed_set.emplace(new_ter);
        lk->ter_id=new_ter;
        Dfs_virLink(i,lk);
        lk=temp_lk;
    }
}

Path virtual_graph::pulse_findPath(NodeId from, NodeId to){
    bool *visited=new bool[num_nodes_];
    for(int i=0;i<num_nodes_;i++) visited[i]=false;
    visited[from]=true;
    Path p;
    virtual_link *lk=new virtual_link(from,from);
    Dfs(to,lk,p);
    delete [] visited;
    delete lk;
    return p;
}

void virtual_graph::Dfs(NodeId end,virtual_link *edge, Path p){
    if(edge->ter_id==end){
        if(p.delay<minDelay){
            minDelay=p.delay;
            pathList.push(p);
        }
        return;
    }

    if(!judge(edge,p)) return;

    p.curNode=edge->ter_id;
    p.path_info.emplace_back(edge->ter_id);
    p.cost +=edge->cost;
    p.delay +=edge->delay;

    for(virtual_link *link:virtual_adjList[edge->ter_id]){
        Dfs(end, link,p);

    }

}

bool virtual_graph::judge(virtual_link *edge,Path p){
    if(p.delay+edge->delay>minDelay) return false;
    if(intersection(edge->C_units,p.C_units).empty()) return false;
    return true;
}

std::vector<int> virtual_graph::intersection(std::vector<int> v1, std::vector<int> v2){
    std::unordered_set<int> result_set; // 用于存放结果
    std::unordered_set<int> nums_set(v1.begin(), v1.end());
        for (int num : v2) {
            // 发现v2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
    return std::vector<int>(result_set.begin(), result_set.end());
}